
class UnionFind:
    def __init__(self, n):
        self.father = [i for i in range(n)]
    def find(self, i):
        if self.father[i] != i:
            self.father[i] = self.find(self.father[i])
        return self.father[i]
    def is_same_set(self, i, j):
        return self.find(i) == self.find(j)
    def union(self, i, j):
        self.father[self.find(i)] = self.find(j)

def kruskal(num_vertices, edges):
    # 对边按权值从小到大排序
    edges.sort(key=lambda x: x[2])
    mst = []
    uf = UnionFind(num_vertices)
    for u, v, w in edges:
        if not uf.is_same_set(u, v):
            uf.union(u, v)
            mst.append((u, v, w))
            if len(mst) == num_vertices - 1:
                break
    return mst

# 最小生成树的边: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]
# 最小生成树的总权值: 19
# 示例使用
num_vertices = 4
edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
mst = kruskal(num_vertices, edges)
print("最小生成树的边:", mst)
total_weight = sum([w for _, _, w in mst])
print("最小生成树的总权值:", total_weight)